The present invention generally relates to cryptosystems, and more particularly relates to private-key stream cipher cryptosystems which employ at least one pseudo-random number generator (PRNG) and post-processing cryptographic isolator to obscure the PRNG state. The combination of PRNG and isolator produces pseudo-random bit keystreams for combining with plaintext to encrypt the plaintext into ciphertext and for combining with the ciphertext to decipher the ciphertext into plaintext.
Cryptosystems perform cryptography to transform plaintext into ciphertext so that only an authorized receiver can transform the ciphertext back into the original plaintext. Encryption or enciphering is the process that transforms plaintext into ciphertext. Decryption or deciphering is the process that transforms ciphertext into plaintext.
A parameter called an encryption key is employed by a cryptosystem to prevent the plaintext from being easily revealed by an unauthorized person. A sender transforms a given plaintext into a large variety of possible ciphertext selected by the specific encryption key. A receiver of the ciphertext deciphers the ciphertext by employing a parameter referred to as a decryption key. In a publickey cryptosystem, the encryption key is made public while the decryption key is kept secret. Therefore, in public key cryptosystems, the decryption key must be computationally infeasible to deduce from the encryption key. In a private-key cryptosystem, the sender and the receiver typically share a common key that is used for both enciphering and deciphering. In such a private-key cryptosystem, the common key is alterable and must be kept secret.
Private-key cryptosystems are typically implemented as block cipher cryptosystems or stream cipher cryptosystems. Block cipher cryptosystems divide the plaintext into blocks and encipher each block independently using a stateless transform. In block cipher cryptosystems if one fixed common private-key is employed to encipher different occurrences of a particular plaintext block, all of these occurrences are encrypted into identical corresponding ciphertext blocks. Therefore, the block size is preferably selected to be large enough to frustrate attacks from a crytanalysis, which analyzes the occurrence frequencies of various patterns among the ciphertext blocks. Example block sizes are 64 bits and 128 bits.
In stream cipher cryptosystems, the plaintext is typically encrypted on a bit-by-bit or word-by-word basis using a stateful transform that evolves as the encryption progresses. In encrypting the plaintext binary data sequence for transmission as a ciphertext binary data sequence, the common private-key is a parameter which controls a pseudo-random number generator (PRNG) to create a long sequence of binary data referred to as a keystream. The stream cipher cryptosystem includes a cryptographic combiner, which combines the keystream with the plaintext sequence. The cryptographic combiner is typically implemented with exclusive-or (XOR) bit-wise logic gates, which perform bit-wise modulo-2 addition. The cryptographic combiner produces the ciphertext. At the receiver, the common private-key controls a receiver PRNG to produce a decryption keystream. The decryption keystream is combined with a decryption combiner to decrypt the ciphertext to provide the plaintext to the receiver. The receiver decryption combiner operation must be the inverse of the sender encryption combiner operation. For this reason, the most common combiner operation is bit-wise XOR which is its own inverse.
One problem with stream cipher cryptosystems is the difficulty of generating a long, statistically uniform, and unpredictable sequence of binary data in the keystream from a short and random key. Such sequences are desirable in the keystream in cryptography to make it impossible, given a reasonable segment of its data and sufficient computer resources, to find out more about the sequences.
There are three general requirements for cryptographically secure keystream PRNGs. First, the period of a keystream must be large enough to accommodate the length of the transmitted message. Second, the keystream output bits must be easy to generate. Third, the keystream output bits must be hard to predict. For example, given the PRNG and the first N output bits, a(0), a(1), . . . , a(Nxe2x88x921), it should be computationally infeasible to predict the (N+1)th bit a(N) in a sequence with better than a 50xe2x80x9450 chance. In otherwords, a cryptanalyst should not be able to generate other forward bits or backward bits if presented with a given portion of the keystream output sequence.
The PRNG employed in stream cipher cryptosystems, often employs a feedback shift register (FSR) which includes N storage elements and a feedback function that expresses each new element a(t) of the sequence, in terms of the previous generated elements a(txe2x88x92N), a(txe2x88x92N+1), . . . , a(txe2x88x921). Each individual storage element of the FSR is called a stage, and the binary signals a(0), a(1), a(2), . . . , a(Nxe2x88x921) are loaded into the stages as initial data to generate the Keystream sequence. The period of the keystream sequence produced by the FSR depends both on the number of stages and on the details of the feedback function. The maximal period of a keystream sequence generated by an N-stage FSR with a non-singular feedback function is 2N, which represents the number of possible states of the N-stage FSR.
Depending on whether the feedback function is linear or is non-linear, the FSR is referred to respectively as a linear feedback shift register (LFSR) or a non-linear feedback shift register (NLFSR).
In particular, the LFSR is employed in many PRNGs for stream cipher cryptosystems. The LFSR feedback function is of the form a(t)=c1 a(txe2x88x921) XOR c2 a(txe2x88x922) XOR . . . XOR CNxe2x88x921 a(txe2x88x92N+1) XOR a(txe2x88x92N), where cj is an element of the set {0,1}. The feedback function of an LFSR can be represented formally by what is referred to as a feedback polynomial:
xe2x80x83f(x)=1+c1x+c2xNxe2x88x922+ . . . +cNxe2x88x921xNxe2x88x921+xN
where the intermediate x has no other meaning than as a mathematical symbol. This feedback polynomial decides the period and the statistical behavior of the keystream output sequence. To avoid trivial output, the zero-state should be excluded from the initial setting. This limits the largest possible period of an LFSR to 2Nxe2x88x921.
In general, to generate the largest possible period 2Nxe2x88x921 for the output sequence, the feedback polynomial f(x) of the LFSR should be primitive. A sequence generated by an LFSR with a primitive feedback polynomial is referred to as a maximal-length LFSR sequence or simply an m-sequence. However, m-sequences cannot be used as keystreams without undergoing further cryptographic transformation. Without this further cryptographic transformation, the key of secrecy (i.e., the initial state of the LFSR and the feedback function of the LFSR) of an N-stage LFSR can be determined from just 2N successive bits of the output sequence.
Efficient synthesis procedures exist for finding feedback polynomials of the shortest LFSR that would generate a given output sequence. The length of such an LFSR is referred to as the linear complexity of the sequence. As a result, an LFSR suitable for employment in a cryptosystem, must guarantee a large enough key independent lower bound to the linear complexity of the sequences the LFSR generates.
The xe2x80x9cknown plaintextxe2x80x9d cryptanalysis attack combines known or guessed plaintext with ciphertext to recover the keystream. Recovering 2N bits destroys the secrecy of an LFSR. Therefore, maximal-length LFSR output sequences cannot be used as keystreams without undergoing further cryptographic transformation. A common method for providing this further cryptographic transformation is to add cryptographic isolators, which provide post-processing of the output of an LFSR. Other methods of cryptographic transformation include non-linear combining of the plaintext and keystream, non-linear combining of multiple LFSRs, and clock control of the LFSR(s). In particular, the cryptographic isolator provides security against certain types of attacks by cryptanalysis. The cryptographic isolator is typically implemented as a non-linear filter. The non-linear filter combines some output bits of the LFSR with some other LFSR output bits, previous plaintext, ciphertext, or other data using a non-linear function to provide the keystream to the cryptographic combiner. The non-linear filter is a one-way function to provide further security in the keystream by making it computationally very expensive for a cryptanalyst to attempt to go backwards or preferably by making it impossible to go backwards to determine the inputs of the cryptographic isolator based on the outputs of the cryptographic isolator.
Conventional cryptographic one-way functions are typically very complex and quite slow for various reasons. Cryptosystems typically require cryptographic isolators to have length preservation. Length preservation means that the number of output bits from the cryptographic isolator are equal to the number of input bits into the cryptographic isolator.
Cryptosystems also typically require that the cryptographic isolator one-way function add little or no bias to the output of the cryptographic isolator. No bias in the output of the cryptographic isolator means that if the input to the cryptographic isolator is uniformly distributed, the output is or is nearly uniformly distributed.
Another desirable property for the cryptographic isolator one-way function is diffusion or avalanche. The diffusion or avalanche property requires that each output bit from the cryptographic isolator one-way function be a function of every input bit to the cryptographic isolator. Conventional cryptographic isolators which achieve length preservation, add little or no bias to the output bits, and further provide full or nearly full diffusion are very complex to implement, and as a result, are quite expensive in terms of hardware resources or software execution time, and produce output bits at a very slow rate.
For reasons stated above and for other reasons presented in greater detail in the Description of the Preferred Embodiments section of the present specification, a stream cipher cryptosystem is desired which includes a PRNG cryptographic isolator to produce pseudo-random bit keystreams with length; preservation, little bias, and full or nearly full diffusion, where the cryptographic isolator is not as complex as conventional cryptographic isolators and operates at a faster rate than conventional cryptographic isolators.
The present invention provides a stream cipher cryptosystem including a pseudo-random number generator (PRNG) receiving a key and providing a vulnerable keystream, and a non-linear filter cryptographic isolator to convert the vulnerable keystream into a protected keystream. The non-linear filter cryptographic isolator includes a multiplier for performing a multiplication function on the PRNG vulnerable keystream to provide a partial product array having a lower partial product array and an upper partial product array, and a simple unbiased operation (SUO) for combining the lower partial product array and the upper partial product array to provide the protected keystream. The combination of the multiplication function and the SUO is a one-way function.
In one embodiment, the pseudo-random bit generator includes a linear feedback shift register (LFSR) responsive to the key for providing the vulnerable keystream.
In one embodiment, the stream cipher cryptosystem includes a cryptographic combiner for combining a first binary data sequence and the protected keystream to provide a second binary data sequence.
In encryption operations, the cryptographic combiner is an encryption combiner and the first binary data sequence is a plaintext binary data sequence and the second binary data sequence is a ciphertext binary data sequence. In decryption operations, the cryptographic combiner is a decryption combiner and the first binary data sequence is a ciphertext binary data sequence and the second binary data sequence is a plaintext binary data sequence.
In one embodiment, the non-linear filter cryptographic isolator also includes a state function for providing a state value to the multiplier which multiplies the vulnerable keystream and the state value to provide the partial product array.
In one embodiment, the SUO is one of the commonly available dyadic operations (i.e., an operation performing a function on exactly two inputs), such as addition, subtraction, exclusive-or, or exclusive-nor, which combines two same sized inputs into an output that is also the same size in manner that does not add any bias (i.e., if the inputs are uniformly distributed, the output is uniformly distributed). In one embodiment, the SUO is performed with a look-up table. The combination of the multiplier operation and the SUO is not an invertible function. In one embodiment, the non-linear filter cryptographic isolator selects the SUO from various SUOs, such as an addition operation, a subtraction operation, an exclusive-or operation, and exclusive-nor operation after each multiply. In one embodiment, the selection is pseudo-random. In one embodiment, the selection is deterministic.
The combination of multiply and SUO produces only a small bias except for one output value which can be up to three times more frequent than the mean output frequency. This value is produced whenever one of the inputs is zero. The value produced depends on the SUO, e.g., exclusive-or produces a: zero while exclusive-nor produces a bit vector of all one""s. In one embodiment, the non-linear filter cryptographic isolator tests the keystream for an output that is more likely to occur, and when found, the non-linear filter cryptographic isolator replaces the output that is more likely to occur with an unbiased value such, as the input or some function of the input.
In one embodiment, a state function receives PRNG output data and combines the previous state value with the PRNG output data using one""s complement addition to provide the next state value. The state value is used as an input to the multiply. In one embodiment, an initialization vector is provided to the state function to initialize the state value to a non-zero value, which remains nonzero because of the use of the one""s complement operation. In one embodiment, both inputs to the multiply are non-zero initialized one""s complement running sums.
In one embodiment, a state function receives the partial product array and performs a function on the partial product array to provide the state value. In one embodiment, the non-linear filter cryptographic isolator divides PRNG output data into a first portion and a second portion and the multiplication function includes multiplying the first portion and the second portion.
The stream cipher cryptosystem according to the present invention includes the non-linear filter cryptographic isolator having the multiplication function, which produces pseudo-random bit keystreams with little bias, full diffusion, and optionally with length preservation. Moreover, the non-linear filter cryptographic isolator having the multiplication function according to the present invention is not as complex as conventional cryptographic isolators and operates at a faster rate than conventional cryptographic isolators of comparable security.